package com.sort;

import java.util.Arrays;

/**
 * 选择排序
 */

public class SelectionSort implements Sort {
    public static void main(String[] args) {
        int[] arr = {
                1, 2, 4, 3, 56, 456, 78, 9123, 4565
        };

        for (int j : arr) {
            System.out.print(j + "\t");
        }
        System.out.println();

        int[] run = new SelectionSort().run(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(run[i] + "\t");
        }

    }


    /**
     * 选择排序
     *
     * @param ar 传进来一个int数组
     * @return 返回排序成功后的int数组
     */
    @Override
    public int[] run(int[] ar) {

//      拷贝数组   不改变原有数组的数据
        int[] arr = Arrays.copyOf(ar,ar.length);

//        定义最小的index
        int minIndex;

//        数组的长度
        int len = arr.length;
//      数据交换时的临时值
        int temp;

        for (int i = 0; i < len - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[minIndex] > arr[j]) {
//                    找到目前最小元素的下标
                    minIndex = j;
                }
            }

 //         将找到的最小值和i位置所在的值进行交换
//            if 是为了 稳定性    虽然选择排序 是不稳定的 但是尽量不要改变稳定性
            if (minIndex != i) {
                temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }

        }
        return arr;
    }
}
